﻿#include <iostream>
using namespace std;
#include <algorithm>
#include <vector>
#include "AVLTree.h"


int main()
{
	//AVLTree<int, int> t1;
	//int a[] = { 8, 1, 10, 6, 4, 7, 14, 13 , 3, 0};
	//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };
	//for (auto& e : a)
	//	t1.Insert({ e,e });
	//
	//t1.InOrder();
	//cout << t1.IsBalance() << endl;

	//auto ret = t1.Find(1);
	//if (ret != nullptr)
	//	cout << "Find: " << ret->_kv.first << endl;
	//else
	//	cout << "No Find this var" << endl;
	//cout << "Hight: " << t1.Hight() << endl;
	//cout << "Size: " << t1.Size() << endl;

	const int N = 100000000;
	vector<int> v;
	v.reserve(N);
	srand(time(0));

	for (size_t i = 0; i < N; i++)
	{
		v.push_back(rand() + i);
		//cout << v.back() << endl;
	}

	size_t begin2 = clock();
	AVLTree<int, int> t;
	for (auto e : v)
	{
		t.Insert(make_pair(e, e));
		//cout << "Insert:" << e << "->" << t.IsBalance() << endl;
	}
	size_t end2 = clock();

	cout << "Insert:" << end2 - begin2 << endl;
	//cout << t.IsBalance() << endl;

	cout << "Height:" << t.Hight() << endl;
	cout << "Size:" << t.Size() << endl;

	size_t begin1 = clock();
	// 确定在的值
	for (auto e : v)
	{
		t.Find(e);
	}

	// 随机值
	/*for (size_t i = 0; i < N; i++)
	{
		t.Find((rand() + i));
	}*/

	size_t end1 = clock();

	cout << "Find:" << end1 - begin1 << endl;

	return 0;
}